package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC62 {

    public int uniquePathsT(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }

        if (m == 1 || n == 1) {
            return 1;
        }

        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }

    public int uniquePaths(int m, int n) {
        if (m < n) {
            int temp = n;
            n = m;
            m = temp;
        }

        long divider = 1, up = 1;
        for (int i = 1; i <= n - 1; i++) {
            divider *= i;
        }
        for (int i = m; i <= m + n - 2; i++) {
            up *= i;
        }

        return (int) (up / divider);
    }


    public static void main(String[] args) {
        LC62 an = new LC62();

//        System.out.println(6402373705728000L / (362880 * 362880L));

        System.out.println(an.uniquePathsT(10, 10));
        System.out.println(an.uniquePaths(10, 10));
    }
}
